package argo.hot100.linklist;

public class SortList {


    public ListNode sortList(ListNode head) {
        return sort(head);

    }

    public ListNode sort(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode rightHead = slow.next;
        slow.next = null;

        ListNode list1 = sort(head);
        ListNode list2 = sort(rightHead);
        return merge(list1, list2);

    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        while (head1 != null && head2 != null) {
            if (head1.val > head2.val) {
                p.next = head2;
                head2 = head2.next;
            } else {
                p.next = head1;
                head1 = head1.next;
            }
            p = p.next;
        }

        p.next = head1 != null ? head1 : head2;
        return dummy.next;
    }

}
